package main.leetcode.clockin.March;

import java.util.Arrays;

/**
 * 945.使数组唯一的最小增量
 *
 * <p>给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
 *
 * <p>返回使 A 中的每个值都是唯一的最少操作次数。
 *
 * <p>示例 1: 输入：[1,2,2] 输出：1 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。
 *
 * <p>示例 2: 输入：[3,2,1,2,1,7] 输出：6 解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。 可以看出 5 次或 5 次以下的 move
 * 操作是不能让数组的每个值唯一的。
 *
 * <p>提示：0 <= A.length <= 40000，0 <= A[i] < 40000
 */
public class day22 {
    public static void main(String[] args) {
        System.out.println(
                new day22().minIncrementForUnique(new int[] {4, 4, 7, 5, 1, 9, 4, 7, 3, 8}));
    }

    // 超出时间限制 哈哈（
    //    public int minIncrementForUnique(int[] A) {
    //        int n = A.length;
    //        if (n < 2) return 0;
    //        HashSet<Integer> hashSet = new HashSet<>();
    //        int move = 0, tmp;
    //        for (int i = 0; i < n; i++) {
    //            tmp = A[i];
    //            while (!hashSet.add(tmp++)) {
    //                ++move;
    //            }
    //        }
    //        return move;
    //    }

    // 只要满足排序后后一位比前一位至少大1就可以
    public int minIncrementForUnique1(int[] A) {
        int n = A.length;
        if (n < 2) return 0;
        int move = 0;
        int[] B = A.clone();
        Arrays.sort(B);
        int tmp;
        for (int i = 1; i < n; i++) {
            if (B[i] <= B[i - 1]) {
                tmp = B[i - 1] - B[i] + 1;
                move += tmp;
                B[i] += tmp;
            }
        }
        return move;
    }

    // 数组计数
    public int minIncrementForUnique(int[] A) {
        if (A.length < 2) return 0;
        int[] counts = new int[50000];
        for (int i : A) counts[i]++;
        int move = 0, tmp;
        for (int i = 0; i < 50000; i++) {
            if (counts[i] > 1) {
                tmp = counts[i] - 1;
                move += tmp;
                counts[i + 1] += tmp;
            }
        }
        return move;
    }
}
